1. Field of the Invention
This invention relates to the storage, retrieval and organization of multimedia objects in a distributed and federate fashion. These multimedia objects may contain synchronized audio and video information, audio and video in unsynchronized form, general data and executable codes. The storage method used enables scalability and allows efficient managing, naming and administering of multimedia objects in a heterogeneous manner. The present invention relates to a storage method for enhancing retrieval of multimedia objects by minimizing the amount of memory, which the search algorithm must, traversed during data retrieval and storage.
2. Description of the Prior Art
Data processing systems often utilize xe2x80x9ctreesxe2x80x9d structure for data storage. A xe2x80x9ctreexe2x80x9d structure is a structure containing a xe2x80x9crootxe2x80x9d node and a plurality number of xe2x80x9ctreexe2x80x9d and xe2x80x9cleafxe2x80x9d nodes in which there is only one path between any nodes in the tree. In a tree structure, the xe2x80x9crootxe2x80x9d node is in the highest level, the xe2x80x9ctreexe2x80x9d nodes are in an intermediate level and the leaf nodes are in a lowest level. The tree structure may be an efficient way that provides a hierarchy for large segments of data and retrieving specific segment of data. Segments of data are stored in the nodes of the tree structure.
In the case of a 3 level tree structure, the tree structure consists of a xe2x80x9crootxe2x80x9d node as a first level, a second level of tree nodes and a third level of xe2x80x9cleafxe2x80x9d nodes. To store data in this tree structure, main data segment can be stored in the xe2x80x9crootxe2x80x9d node and some other sub-data stored in the xe2x80x9ctreexe2x80x9d nodes. Another sets of nodes under each xe2x80x9ctreexe2x80x9d nodes are further categorized into xe2x80x9cleafxe2x80x9d nodes of the respective xe2x80x9ctreexe2x80x9d nodes. In order for storage and retrieval of data segment in a tree structure, the tree structure is traversed. To allow traversal nodes in the tree structure where the data segments reside, each node in the tree structure must carry sufficient pointer information for the memory location of lower layer xe2x80x9ctreexe2x80x9d nodes or xe2x80x9cleafsxe2x80x9d nodes. The pointer information is referred to as the link of the nodes. For the xe2x80x9crootxe2x80x9d node and each xe2x80x9ctreexe2x80x9d node in a tree structure, there must be N number of memory pointers to register the location of each node at a lower layer which contains N number xe2x80x9ctreexe2x80x9d or xe2x80x9cleafxe2x80x9d nodes. As a consequence, there is a tendency for the xe2x80x9crootxe2x80x9d node and xe2x80x9ctreexe2x80x9d nodes in a tree structure of arbitrary size in terms of nodes to have a limited number of xe2x80x9ctreexe2x80x9d or xe2x80x9cleafxe2x80x9d nodes for the adjacent level of nodes.
While other some tree structure requires a xe2x80x9cbalancedxe2x80x9d structure, that is, a tree structure in which all but the bottom nodes are completely filled. It could be possible to map an xe2x80x9cunbalancedxe2x80x9d tree structure to a balanced tree structure by introducing null nodes into the xe2x80x9cbalancedxe2x80x9d tree structure By doing this, redundancy is introduced. Introducing null nodes has a harmful effect on the memory size requirement of virtual memory data processing systems, wherein fixed-length blocks of memory often referred to as xe2x80x9cpagexe2x80x9d are utilized. Each node of a tree memory in a virtual memory may result in none continuous storage of nodes because of redundant nodes being introduced. In the virtual memory, this may result in a page fault, if xe2x80x9cpagingxe2x80x9d is utilized, which greatly increase the amount of time required to retrieve data within a tree structure.
To represent a tree structure in a graph node, as discussed in xe2x80x9cData Structure and Algorithm Analysis in Cxe2x80x3, Benjamin/Cummings publishing Co., Inc, 1993, requires 2 memory pointers to store the location of ""siblingxe2x80x9d and xe2x80x9cchildxe2x80x9d node. Sibling node is a node in the same level while xe2x80x9cchildxe2x80x9d node is a node in a lower level of the tree structure. Using 2 pointers allows allocation of memory of the xe2x80x9cleafxe2x80x9d nodes to be located in non-adjacent memory location. Again this has a deleterious effect on the paging scheme used in the virtual memory as described in the preceding paragraph.
The present invention provides a method of providing an efficient data storage and data retrieval while retaining the hierarchy of a tree, eliminating the problem of conventional branches to facilitate searching and to improve multimedia objects retrieval by preventing the problem of page faults which may encountered during traversing from occurring.
The present invention provides an improved method of solving the problem encountered in managing and allocating pointer memory of xe2x80x9crootxe2x80x9d node and each xe2x80x9ctreexe2x80x9d node for adjacent level of xe2x80x9cleafxe2x80x9d nodes and xe2x80x9ctreexe2x80x9d nodes in a multilevel tree structure. In conventional methods, more than 2 memory pointers are required for each xe2x80x9ctreexe2x80x9d node to retain the hierarchical structure of a tree. The present invention uses a single pointer memory location to store the location of next node while still retaining a substantial amount of information of the tree structure.
The present invention also provides a method for preventing multimedia objects from random fragmentation found during storing and retrieving data fragmented in segments of smaller pieces of data of unequal size in the case where each data segment has a strong coupling which can be best represented in a hierarchical form.
The present invention provides means to reduce the complexity of a tree structure by decomposing a highly complex and unmanageable tree structure into a highly manageable format that aids in retrieval of multimedia objects that are strongly coupled or data that are related with minimal memory paging fault.
This invention provides an improved method and system for enhancing data retrieval and storage in a multilevel tree structure by significantly reducing the required amount of time and memory that must be traversed during data retrieval and data storage for both depth-first and breath-first search.
To resolve the problems outlined in the above section, the invented method and system provides means of decomposing a tree structure of any arbitrary form into a graph map with either breath or depth coupling by mapping nodes of the tree structure into nodes with a single vertex; means of organizing the nodes in the graph map into page memory to improve paging during data retrieval; means to traverse efficiently with minimal paging fault for data or multimedia objects with strong coupling; means of traversing in depth-first search in a depth coupled graph map without page fault using an efficient traversing algorithm; and means of traversing in a breadth-first search in a breadth coupled graph map without page fault using an efficient traversing algorithm.
Storage of multimedia objects organized in a hierarchical ordered tree nodes is efficiently performed by decomposing the tree nodes organized in a conventional tree structure into graph nodes with a single-link to register location of graph nodes which is a representative of child tree nodes. The multimedia objects organized in a series of single-link graph nodes can then be stored in a distributed and federated manner providing a system for managing and administering the multimedia objects. The graph nodes are compacted into page memory based on either a depth coupled or breadth coupled multimedia objects to minimized paging fault during multimedia objects retrieval. To enable fast retrieval of the multimedia objects organized in a sequence of graph nodes, a depth-first and breadth-first algorithm is designed to enable fast retrieval and browsing of the specific multimedia objects stored in page memory as graph nodes.
As used herein, the use of the terms xe2x80x9cfederatedxe2x80x9d or xe2x80x9cfederated mannerxe2x80x9d refer to a manner whereby multimedia objects organized as different branches of a tree structure are managed by different entities. In other words, xe2x80x9cfederatedxe2x80x9d refers to a structure where different entities manage different branches or parts of a tree structure. As used herein, the use of the phrases xe2x80x9cdistributedxe2x80x9d or xe2x80x9cdistributed mannerxe2x80x9d refer to a manner whereby the different parts or branches of a tree structure (i.e. multimedia objects organized into a tree with logical inter-connections) are managed by a single entity. As used herein, xe2x80x9cdepth coupledxe2x80x9d refers to vertical linkage of multimedia content whose objects are arranged in a tree structure, such as a root-tree link or a tree-leaf link for example. As used herein, xe2x80x9cbreadth coupledxe2x80x9d refers to horizontal linkage of multimedia content whose objects are arranged in a tree structure, as is used to indicate two objects at the same level within a branch for example.